Java 编程技巧之数据结构

作者 | 常意

责编 | 屠敏

导读

唐宋八大家之一欧阳修在《 卖油翁 》中写道：

编写代码的”老司机”也是如此，”老司机”之所以被称为”老司机”，原因也是”无他，唯手熟尔”。 编码 过程中踩过的坑多了，获得的编码经验也就多了，总结的编码技巧也就更多了。总结的编码技巧多了，凡事又能够举一反三，编码的速度自然就上来了。笔者从数据结构的角度，整理了一些 Java 编程技巧，以供大家学习参考。

使用HashSet判断主键是否存在

HashSet 实现 Set 接口，由哈希表（实际上是 HashMap ）实现，但不保证 set 的迭代顺序，并允许使用 元素。HashSet 的时间复杂度跟 HashMap 一致，如果没有哈希冲突则时间复杂度为 O(1) ，如果存在哈希冲突则时间复杂度不超过 O(n) 。所以，在日常编码中，可以使用 HashSet 判断主键是否存在。

案例：给定一个字符串(不一定全为字母)，请返回第一个重复出现的字符。

其中，由于 Set 的 add 函数 有个特性——如果添加的元素已经再集合中存在，则返回 false 。可以简化代码为：

使用HashMap存取键值映射关系

简单来说，HashMap 由数组和 链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。如果定位到的数组位置不含链表，那么查找、添加等操作很快，仅需一次寻址即可，其时间复杂度为 O(1) ；如果定位到的数组包含链表，对于添加操作，其时间复杂度为 O(n) ——首先遍历链表，存在即覆盖，不存在则新增；对于查找操作来讲，仍需要遍历链表，然后通过key对象的 equals 方法逐一对比查找。从性能上考虑， HashMap 中的链表出现越少，即哈希冲突越少，性能也就越好。所以，在日常编码中，可以使用 HashMap 存取键值映射关系。

案例：给定菜单记录列表，每条菜单记录中包含父菜单标识（根菜单的父菜单标识为 ），构建出整个菜单树。

使用 ThreadLocal 存储 线程 专有对象

ThreadLocal 提供了线程专有对象，可以在整个线程生命周期中随时取用，极大地方便了一些逻辑的实现。

常见的 ThreadLocal 用法主要有两种：

1、保存线程上下文对象，避免多层级参数传递；

2、保存非 线程安全 对象，避免多线程并发调用。

保存线程上下文对象，避免多层级参数传递

这里，以 PageHelper 插件的源代码中的分页参数设置与使用为例说明。

设置分页参数代码：

使用分页参数代码：

使用分页插件代码：

如果要把分页参数通过函数参数逐级传给查询语句，除非修改 MyBatis 相关接口函数，否则是不可能实现的。

保存非线程安全对象，避免多线程并发调用

在写日期格式化工具函数时，首先想到的写法如下：

其中，每次调用都要初始化 DateFormat 导致性能较低，把 DateFormat 定义成常量后的写法如下：

由于 SimpleDateFormat 是非线程安全的，当多线程同时调用 formatDate 函数时，会导致返回结果与预期不一致。如果采用 ThreadLocal 定义线程专有对象，优化后的代码如下：

这是在没有线程安全的日期格式化工具类之前的实现方法。在 JDK8 以后， 建议 使用 DateTimeFormatter 代替 SimpleDateFormat ，因为 SimpleDateFormat 是线程不安全的，而 DateTimeFormatter 是线程安全的。当然，也可以采用第三方提供的线程安全日期格式化函数，比如 apache 的 DateFormatUtils 工具类。

注意：ThreadLocal 有一定的内存 泄露 的风险，尽量在业务代码结束前调用 remove 函数进行数据清除。

使用 Pair 实现成对结果的返回

在 C/C++ 语言中， Pair （对）是将两个数据类型组成一个数据类型的容器，比如 std::pair 。

Pair 主要有两种用途：

1、把 key 和 value 放在一起成对处理，主要用于 Map 中返回名值对，比如 Map 中的 Entry 类；

2、当一个函数需要返回两个结果时，可以使用 Pair 来避免定义过多的数据模型类。

第一种用途比较常见，这里主要说明第二种用途。

定义模型类实现成对结果的返回

函数实现代码：

函数使用案例：

使用 Pair 类实现成对结果的返回

在 JDK 中，没有提供原生的 Pair 数据结构，也可以使用 Map::Entry 代替。不过， Apache 的 commons-lang3 包中的 Pair 类更为好用，下面便以 Pair 类进行举例说明。

函数实现代码：

函数使用案例：

定义 Enum 类实现取值和描述

在 C++、Java 等计算机编程语言中， 枚举类型 （Enum）是一种特殊数据类型，能够为一个变量定义一组预定义的常量。在使用枚举类型的时候，枚举类型变量取值必须为其预定义的取值之一。

用 class 关键字实现的枚举类型

在 JDK5 之前， Java 语言不支持枚举类型，只能用类（class）来模拟实现枚举类型。

用 enum 关键字实现的枚举类型

JDK5 提供了一种新的类型—— Java 的枚举类型，关键字 enum 可以将一组具名的值的有限集合创建为一种新的类型，而这些具名的值可以作为常量使用，这是一种非常有用的功能。

其实，Enum 类型就是一个语法糖，编译器帮我们做了语法的解析和编译。通过反编译，可以看到 Java 枚举编译后实际上是生成了一个类，该类继承了 java.lang.Enum ，并添加了 values、valueOf 等枚举类型通用方法。

定义 Holder 类实现参数的输出

在很多语言中，函数的参数都有输入（in）、输出（out）和输入输出（inout）之分。在 C/C++ 语言中，可以用对象的引用（&）来实现函数参数的输出（out）和输入输出（inout）。但在 Java 语言中，虽然没有提供对象引用类似的功能，但是可以通过修改参数的字段值来实现函数参数的输出（out）和输入输出（inout）。这里，我们叫这种输出参数对应的数据结构为Holder（支撑）类。

Holder 类实现代码：

Holder 类使用案例：

其实，可以实现一个 泛型 支撑类，适用于更多的数据类型。

定义 Union 类实现数据体的共存

在 C/C++ 语言中，联合体（union），又称共用体，类似 结构体 （struct）的一种数据结构。联合体（union）和结构体（struct）一样，可以包含很多种数据类型和变量，两者区别如下：

1、结构体（struct）中所有变量是“共存”的，同时所有变量都生效，各个变量占据不同的内存空间；

2、联合体（union）中是各变量是“互斥”的，同时只有一个变量生效，所有变量占据同一块内存空间。

当多个数据需要共享内存或者多个数据每次只取其一时，可以采用联合体（union）。

在Java语言中，没有联合体（union）和结构体（struct）概念，只有类（class）的概念。众所众知，结构体（struct）可以用类（class）来实现。其实，联合体（union）也可以用类（class）来实现。但是，这个类不具备“多个数据需要共享内存”的功能，只具备“多个数据每次只取其一”的功能。

这里，以 微信 协议的客户消息为例说明。根据我多年来的接口协议封装经验，主要有以下两种实现方式。

使用函数方式实现 Union

Union 类实现:

Union 类使用:

主要优缺点:

优点：更贴近 C/C++ 语言的联合体（union）；

缺点：实现逻辑较为复杂，参数类型验证较多。

使用继承方式实现 Union

Union 类实现:

Union 类使用:

主要优缺点:

优点：使用虚基类和子类进行拆分，各个子类对象的概念明确；

缺点：与 C/C++ 语言的联合体（union）差别大，但是功能上大体一致。

在 C/C++ 语言中，联合体并不包括联合体当前的数据类型。但在上面实现的 Java 联合体中，已经包含了联合体对应的数据类型。所以，从严格意义上说， Java 联合体并不是真正的联合体，只是一个具备“多个数据每次只取其一”功能的类。

使用泛型屏蔽类型的差异性

在 C++ 语言中，有个很好用的模板（template）功能，可以编写带有参数化类型的通用版本，让编译器自动生成针对不同类型的具体版本。而在 Java 语言中，也有一个类似的功能叫泛型（generic）。在编写类和方法的时候，一般使用的是具体的类型，而用泛型可以使类型参数化，这样就可以编写更通用的代码。

许多人都认为， C++ 模板（template）和 Java 泛型（generic）两个概念是等价的，其实实现机制是完全不同的。 C++ 模板是一套宏指令集，编译器会针对每一种类型创建一份模板代码副本； Java 泛型的实现基于”类型擦除”概念，本质上是一种进行类型限制的语法糖。

泛型类

以支撑类为例，定义泛型的通用支撑类：

泛型接口

定义泛型的数据提供者接口：

泛型方法

定义泛型的浅拷贝函数：

泛型 通配符

泛型通配符一般是使用”？”代替具体的类型实参，可以把”？”看成所有类型的父类。当具体类型不确定的时候，可以使用泛型通配符 “？”；当不需要使用类型的具体功能，只使用Object类中的功能时，可以使用泛型通配符 “？”。

在 Java 规范中，不 建议 使用泛型通配符”？”，上面函数可以改为：

泛型上下界

在使用泛型的时候，我们还可以为传入的泛型类型实参进行上下界的限制，如：类型实参只准传入某种类型的父类或某种类型的子类。泛型上下界的声明，必须与泛型的声明放在一起 。

上界通配符（extends）：

上界通配符为 ”extends ”，可以接受其指定类型或其子类作为泛参。其还有一种特殊的形式，可以指定其不仅要是指定类型的子类，而且还要实现某些接口。例如： List